package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC427 {
    public long startExecuteTime = System.currentTimeMillis();


    // Definition for a QuadTree node.
    class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;


        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    }

    class Solution {
        public Node construct(int[][] grid) {
            return constructRecur(grid, 0, 0, grid.length - 1, grid.length - 1);
        }

        public Node constructRecur(int[][] grid, int startX, int startY, int endX, int endY) {
            if (endX <= startX) return new Node(grid[startX][startY] == 1, true);
            int size = endX - startX + 1;
            Node topLeft = constructRecur(grid, startX, startY, endX - size / 2, endY - size / 2);
            Node topRight = constructRecur(grid, startX, startY + size / 2, endX - size / 2, endY);
            Node bottomLeft = constructRecur(grid, startX + size / 2, startY, endX, endY - size / 2);
            Node bottomRight = constructRecur(grid, startX + size / 2, startY + size / 2, endX, endY);
            boolean isLeaf = topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val
                    && topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf;
            if (isLeaf) return new Node(topLeft.val, true);
            return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] arr = InputUtil.toDoubleIntegerArray("[[1,1,0,0],[0,0,1,1],[1,1,0,0],[0,0,1,1]]");
        Node root = solution.construct(arr);
        System.out.println(root);
    }

    public static void main(String[] args) throws Exception {
        LC427 an = new LC427();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
